import java.util.HashMap;
import java.util.Map;

/*
 * @lc app=leetcode.cn id=1 lang=java
 *
 * [1] 两数之和
 */

// @lc code=start
class Solution {
    // HashMap 优化
    // (1ms, 99%, 41MB, 67%)
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[] { map.get(target - nums[i]), i };
            }
            map.put(nums[i], i);
        }
        return new int[2];
    }
}
// @lc code=end

// 使用HashMap
// (49ms,41.6MB,5%,5%)
// public int[] twoSum(int[] nums, int target) {
// Map<Integer, Integer> map = genMap(nums, target);
// int[] result = new int[2];
// map.forEach((key, value) -> {
// int next = target - value;
// if (map.containsValue(next)) {
// map.forEach((key2, value2) -> {
// if (value2 == next && key != key2) {
// result[0] = key;
// result[1] = key2;
// }
// });
// }
// });
// return result;
// }

// private Map<Integer, Integer> genMap(int[] nums, int target) {
// Map<Integer, Integer> map = new HashMap();
// int len = nums.length;
// for (int i = 0; i < len; i++) {
// map.put(i, nums[i]);
// }
// return map;
// }

// 双层For循环
// (49ms,38%,41.6MB,26%)
// public int[] twoSum(int[] nums, int target) {
// int len = nums.length;
// for (int i = 0; i < len - 1; i++) {
// for (int j = i + 1; j < len; j++) {
// if (nums[i] + nums[j] == target)
// return new int[] { i, j };
// }
// }
// return new int[2];
// }